#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 1e4 + 5;

int n, k;
int a[N];
int mx[5505][505];
int dp[N][505];
int lowbit(int x) { return x & -x; }
void update(int x, int y, int d) {
  for (int i = x; i <= 5500; i += lowbit(i)) {
    for (int j = y; j <= k + 1; j += lowbit(j)) {
      mx[i][j] = max(mx[i][j], d);
    }
  }
}
int query(int x, int y) {
  int ans = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    for (int j = y; j > 0; j -= lowbit(j)) {
      ans = max(ans, mx[i][j]);
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k;
  rep(i, 1, n) cin >> a[i];
  rep(i, 1, n) {
    per(j, k, 0) {
      int x = a[i] + j;
      dp[i][j] = query(x, j + 1) + 1;
      update(x, j + 1, dp[i][j]);
    }
  }
  cout << query(5500, k + 1);
  return 0;
}